import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        int[][] mat = {{1,2,3} ,{4,5,6},{7,8,9}};
        System.out.println(Arrays.deepToString(matrixBlockSum(mat, 1)));
    }
    public static int[][] matrixBlockSum(int[][] mat, int k) {
         
          int n = mat.length ;
          int m = mat[0].length ;
          int[][] mat2 = new int[n+1][m+1] ;
         int[][] nums = new int[n+1][m+1] ; 
         for(int i= 1 ; i <= n ; i ++){
            for(int j= 1 ; j <= m ; j ++){
                mat2[i][j] = mat[i-1][j-1];
                nums[i][j]= mat2[i][j] + nums[i][j-1]+nums[i-1][j] - nums[i-1][j-1] ;
            }
         }
        int[][] sum = new int[n][m] ; 
        for(int i=0 ; i < n ; i ++){
            for(int j = 0 ; j < m ; j ++){
                int x1 = i-k>=0?i-k:0;
                int y1 = j-k>=0?j-k:0;
                int x2 = i+k<n?i+k:n-1 ;
                int y2 = j+k<m?j+k:m-1 ;
                sum[i][j] = nums[x2+1][y2+1] - nums[x1][y2+1] - nums[x2+1][y1]+nums[x1][y1];
            }
        }
    return sum ;

    }
}